/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    if(amount === 0) return 0
    let dp = new Array(amount + 1).fill(Infinity)
    dp[0]=0
    for(let i=1;i<=amount;i++){
        //1.先不考虑边界
        //  1.1 假设dp[i]枚硬币可以构成i的金额，那么再拿一枚硬币可能到达的金额是多少？
        //  1.2 答案是i + coin (coin可能是coins中的每一个值),而i+coin金额对应的硬币数量是dp[i+coin]
        //  1.3 反过来，对于金额i，他有可能是前面某个金额j，加上一枚硬币coin的金额达到的，则i= coin + j, dp[i] = dp[j] + 1
        //  1.4 要求dp[j]的最小值，就是求前面哪一个dp[j]的值最小(因为他们都是 + 一枚硬币的值 到达i的)
        for(let coin of coins){
            //所以这里是看哪一个dp[j]更小，这里访问的是i前面的数，i从小到大增长，所以不出意外的话dp[j]是有值的
            //又因为出现了i-coin，为了不越界，coin<=i
            if(coin<=i){
                dp[i]=Math.min(dp[i-coin]+1,dp[i]) //比较，有更小的就换
            }
        }
    }
    return dp[amount]===Infinity?-1:dp[amount]
};
let coins = [1, 2, 5], amount = 11
console.log(coinChange(coins,amount));